本文改编自斯坦福 CS106L 的一份作业，详细的背景介绍可以参考官方文档。

改版后的初始项目代码不包含迭代器的内容，所以在实现的过程中注意不要使用基于范围的 for 循环进行迭代。虽然使用传统的 for 循环处理略微繁琐，但不失为一个练习的契机。

在完成本项目的练习后，你将有两个选择。其一，继续参考公开的教材和资料，独立完成迭代器的开发工作；其二，斯坦福的初始项目已经包含了完整的迭代器代码实现，可以直接借用，改写本项目代码，体会迭代器开发的过程。

本小节视频讲解时间段 01:04:22-01:15:30

Milestone 0：阅读

初始项目包含如下文件：

HashMap/
	include/
		hashmap.h 包含 HashMap 的定义，在这里添加你的定义
		hashmap_impl.h 包含 HashMap 的实现，在这里添加你的实现
		hashmap_iterator.h 用于后续添加迭代器的代码
		test_settings.h 用于开关每个子任务的默认测试案例
		rang.h 用于终端文本颜色，可忽略
	res/
		short_anser.txt 包含一些简短的问答
	src/
		main.cpp 主函数，可以在这里添加自定义测试
		test.cpp 默认测试案例，原则上不需要修改
		utils.cpp 斯坦福 C++ 库提取的一些使用工具，可忽略

初始项目代码已经完成了部分文档的编写，这些文档包含了大量零碎的知识点，需要参考 C++ 在线文档尝试理解每个部分的意思，特别是 hashmap.h 和 hashmap_impl.h 两个文件。

只有理解了这些代码的设计意图，才能更好地完成后续任务。

Milestone 1：实现 rehash()

本小节视频讲解时间段 00:13:34-00:22:55

第一个需要你完成的函数是 rehash，这个函数的实现需要你对链表的使用有一定的了解，这在 CS101 的作业中已经有了大量的练习。

和 CS101 链表作业的实现要求类似，rehash 的实现同样禁止分配任何内存，还要避免内存泄漏。只能利用现有的节点，通过指针的灵活操作来实现调整节点的目的。在实现的过程中，记得参考 insert 和 erase 的现有实现。

默认提供了 1A 和 1B 两个测试，前者为外部测试，后者为内部测试。内部测试较为粗糙，有一定的失败机率，偶尔发生不用担心。除了这些测试，你还可以添加自己的测试案例。良好的测试，能够让你对自己的代码更有信心。

这个任务完成后，你将对初始项目的代码有更深刻的了解。

Milestone 2：运算符重载和常量正确

此部分你将实现 4 个运算符重载，还有 1 个常量接口问题需要解决。在实现的过程中，记得修改 test_settings.h 文件，依次开启相关的测试案例。

索引 []

索引操作接收一个键（key），并返回映射值（mapped value）的一个引用。索引操作需要支持自动插入，也就是说，当键不存在时，将创建一个默认的映射值，一起组成一个新的键/映射对（key/mapped pair）插入元素。

流插入 <<

流插入操作将 HashMap 的内容输出到输出流中，输出格式可以模仿斯坦福库中的 HashMap：

  • 使用类似 {key1: mapped1, key2: mapped2, ...} 的格式输出所有的元素
  • 输出顺序没有要求，这符合无序映射的特性

更重要的是，流插入操作支持链式插入，例如 cout << map1 << map2 << endl。思考这一点在实现中如何体现。

相等 == 和不相等 !=

如果两个对象的键/映射对完全相同，即包含完全相同的元素，则两个对象相等；反之，则不相等。

如果桶（bucket）大小或元素在桶中的位置不一致，不影响判断结果，只以元素本身作比较。

常量正确

初始代码或你自己添加的成员函数可能不符合常量正确（const correctness）的要求。这一步的任务是找出这些接口并修复。

Milestone 3：拷贝语义和移动语义

初始代码已经包含了构造函数和析构函数；这部分需要你实现拷贝语义和移动语义的几个接口：

  • 拷贝构造函数
  • 拷贝赋值运算符
  • 移动构造函数
  • 移动赋值运算符

拷贝操作需要创建给定对象的相同副本；移动操作需要将给定对象的内容转嫁给当前对象。两个实现都要避免内存泄漏，并尽可能安全高效地实现代码。

关于测试案例，3A 用于测试拷贝操作，3B 用于测试移动操作，3C 用于确认移动操作的效率，实现过程中要避免拷贝。

Milestone 4：问答题

在 res/short_answers.txt 中有 10 个小问题需要你思考。这些问题有助于你更好地理解一些细节问题。

Milestone 5：列表初始化/范围构造器（可选）

Milestone 6：迭代器（可选）